# 	Q9_51. 上一个排列
# 给定一个整数数组来表示排列，找出其上一个排列
# 例1：
# 输入:[1,3,2,3]
# 输出:[1,2,3,3]
# 例2:
# 输入:[1,2,3,4]
# 输出:[4,3,2,1]
# 其他示例：
# 输出  ←  输入
# [1, 2, 3, 6, 5, 4] ←  [1, 2, 4, 3, 5, 6]
# 1,2,3 ← 1,3,2
# 3,2,1 ← 1,2,3
# 1,1,5 ← 1,5,1
# 相关题目
# 388. 第k个排列197. 排列序号52. 下一个排列
# 算法分析
# •	题目要求对于一个整数数组来表示的排列，找出其上一个排列。如果本题用全排列枚举，保存每个排列的方式，明显复杂度过高。
# •	因此，本题可以考虑直接从排列的性质出发，通过模拟的方法，对数组进行操作，找到上一个排列。
# •	首先看一个例子：观察原排列[1, 2, 4, 3, 5, 6]和上一个排列[1, 2, 3, 6, 5, 4]，可以看到原排列中，4是一个分界线。4是从末尾开始往前第一个非下降点，在4之前的元素位置不变，只需要改变4以及4之后的元素。
# •	可以将排列想象成一种特殊的进制，比如从"0099"到"0100"，要更新当前的百位，必然这个位置以后的十位和个位元素均已达到最大。排列中是完全倒序表示最大，所以，我们接下来对原排列4之后的元素进行降序排序。利用排列的性质，将这部分[3, 5, 6]直接翻转即变为降序。此时新的排列为[1, 2, 4, 6, 5, 3]，可以看到离最终的上一个排列结果已经比较接近。
# •	最后一步，我们将4和后面最小的元素进行交换，即排列变为[1, 2, 3, 6, 5, 4]，这个就是上一个排列。
# 算法步骤
# 1.	从原排列末尾开始往前，找到第一个非下降点，作为更新排列的基准点。
# 2.	在这个基准点前面的元素不改变。
# 3.	将这个基准点后面的元素翻转，变为降序排序。
# 4.	找到基准点后面的最小元素，与基准点上的元素进行交换。
# 复杂度
# •	时间复杂度：O(n)，n为数组的元素个数
# o	找基准点，以及对后面的元素进行倒序和查找最小值，均为一重循环遍历。
# •	空间复杂度：O(1)
# o	直接对数组进行操作，不需要中间变量

class Solution:
    def prev_permutation(self, nums):
        if not nums: return []
        n = len(nums)
        i = n - 1
        # 找到离结尾最近的一个底点(等号勿忘！)
        while i > 0 and nums[i] >= nums[i - 1]:
            i -= 1
        # 这种情况说明list已经是完全递增，直接翻转就可以
        if i == 0:
            return list(reversed(nums))
        # 找到底点右边比nums[i - 1]小的数字中最大的一个
        j = n - 1
        while j >= 0 and nums[j] >= nums[i - 1]:  # j>=0勿忘！
            j -= 1
        # 交换两个数字（j & i-1），翻转底点之后的部分
        nums[i - 1], nums[j] = nums[j], nums[i - 1]
        return nums[:i] + list(reversed(nums[i:]))
